<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 
            正数和为 x  负数为target-x    x-(target-x)=sum
            x=(sum+target)/2
            */
            var findTargetSumWays = function (nums, target) {
                nums.sort((a, b) => a - b)
                let sum = nums.reduce((a, b) => (a += b), 0)
                if (Math.abs(target) > sum) return 0
                if ((sum + target) % 2) {
                    return 0 //因为正数和x 一定是整数
                }
                let bagSize = (sum + target) / 2
                let dp = new Array(bagSize + 1).fill(0)
                //初始化方法 dp[0]=1
                dp[0] = 1
                for (let i = 0; i < nums.length; i++) {
                    for (let j = bagSize; j >= nums[i]; j--) {
                        //装满背包有几种方法
                        //当背包容量为5 dp[5]+=dp[5-nums[0]]
                        dp[j] += dp[j - nums[i]]
                    }
                }
                return dp[bagSize]
            }
            findTargetSumWays([1, 1, 1, 1, 1], 3)
        </script>
    </body>
</html>
